package com.linyaonan.leetcode.medium._334;

/**
 * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 * <p>
 * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3,4,5]
 * 输出：true
 * 解释：任何 i < j < k 的三元组都满足题意
 * 示例 2：
 * <p>
 * 输入：nums = [5,4,3,2,1]
 * 输出：false
 * 解释：不存在满足题意的三元组
 * 示例 3：
 * <p>
 * 输入：nums = [2,1,5,0,4,6]
 * 输出：true
 * 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 5 * 10^5
 * -2^31 <= nums[i] <= 2^31 - 1
 *
 * @author: Lin
 * @date: 2024/3/19
 */
public class IncreasingTripletSubsequence {

    /**
     * 会超时，方案废弃
     * @param nums
     * @return
     */
    public boolean increasingTriplet(int[] nums) {
        // 1. 异常边界
        if (nums == null || nums.length < 3) {
            return false;
        }

        // 2. 使用三指针进行求解
        // l1 = 0,l2 为l1+1开始第一个比nums[l1]大的数值，l3从l2+1开始
        // 重复上面的过程直到l1==nums.length-3结束
        // 可以适当剪枝，当l1=k时没有找到，那么只有可能比k小的才能有机会，所以每一次进行记录最小的k，大于等于k的直接跳过
        int k = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < k) {
                if (checkHasIncreasing(nums, i, i + 1, i + 2)) {
                    return true;
                } else {
                    k = Math.min(k, nums[i]);
                }
            }
        }

        return false;
    }

    private boolean checkHasIncreasing(int[] nums, int l1, int l2, int l3) {
        if (l1 > nums.length - 3) {
            return false;
        } else {
            int numsL1 = nums[l1];
            for (int i = l1 + 1; i < nums.length; i++) {
                if (nums[i] > numsL1) {
                    for (int j = i + 1; j < nums.length; j++) {
                        if (nums[j] > nums[i]) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }


    /**
     * 使用前缀和的思路求解，从左向右遍历求出每一个位置i对应的从0~i中的最小值 =>leftMin；从右想左遍历求出每一个位置j对应的从j1 ~ length-1中的最大值 => rightMax
     *
     * 有了这两个辅助数组后，只需要找到k位置存在 leftMin[k-1] < nums[k] < rightMax[k+1] 则直接返回
     *
     * 整体的时间复杂度为 O(N)
     *
     * @param nums
     * @return
     */
    public boolean increasingTriplet2(int[] nums) {
        // 1. 异常边界考虑
        if (nums == null || nums.length < 3) {
            return false;
        }

        // 2. 保存k索引下，从0 ~ k的最小值
        int[] leftMin = new int[nums.length];
        leftMin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }
        // 3. 存储 length - 1 ~ k的最大值
        int[] rightMax = new int[nums.length];
        rightMax[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }

        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }

        return false;

    }

    /**
     * 贪心思路，使用两个变量one，two来存储顺序的结果，并且two > one 只需要找到three > two 直接返回
     *
     * 如果three介于one，two直接，则修改two进行变小
     * 如果three小于one，则将one修改为three，one变小，但是two不变，即two之前还有一个比two小的old one，只需要找到一个新的three比two大直接返回
     *
     * @param nums
     * @return
     */
    public boolean increasingTriplet3(int[] nums) {
        // 1. 异常边界考虑
        if (nums == null || nums.length < 3) {
            return false;
        }

        int one = nums[0];
        int two = Integer.MAX_VALUE;

        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            // 比one小，则更新one
            if (tmp <= one) {
                one = tmp;
            } else if (tmp <= two) {
                // 比one大，比two小，更新two
                two = tmp;
            } else {
                // 比two大直接找到
                return true;
            }
        }
        return false;
    }

}
